package 集合框架中PriorityQueue的比较方式;

/*
集合框架中的PriorityQueue底层使用堆结构，因此其内部的元素必须要能够比大小，PriorityQueue采用了：Comparble和Comparator两种方式。
    1. Comparble是默认的内部比较方式，如果用户插入自定义类型对象时，该类对象必须要实现Comparble接口，并覆写compareTo方法
    2. 用户也可以选择使用比较器对象，如果用户插入自定义类型对象时，必须要提供一个比较器类，让该类实现Comparator接口并覆写compare方法
 */

/*
 使用PriorityQueue创建大堆，解决TOPK问题
 */
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

class Compa implements Comparator<Integer>{
    public int compare(Integer num1, Integer num2) {
        return num2 - num1;
    }
}
public class Test {
    public static int[] smallestK(int[] arr, int k) {
        int[] ret=new int[k];

        if(k==0) return ret;

        //创建大根堆
       Compa compa=new Compa();
       PriorityQueue<Integer> p=new PriorityQueue<>(compa);
        for (int i = 0; i < k; i++) {
            p.offer(arr[i]);
        }
        for (int i = k; i < arr.length; i++) {
            if(arr[i]<p.peek()){
                p.poll();
                p.offer(arr[i]);
            }
        }
        for (int i = 0; i < k; i++) {
            ret[i]=p.poll();
        }
        return ret;
    }

    public static void main(String[] args) {
        int[] array = {4,1,9,2,8,0,7,3,6,5};
        int[] ret = smallestK(array,3);
        System.out.println(Arrays.toString(ret));//[2,1,0]
    }
}
